package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;

import sun.tools.jar.resources.jar;
import util.LogUtils;

/*
 * 
原题　
		Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
	
	Your algorithm's runtime complexity must be in the order of O(log n).
	
	If the target is not found in the array, return [-1, -1].
	
	For example,
	Given [5, 7, 7, 8, 8, 10] and target value 8,
	return [3, 4]. 
	
题目大意
	给定按升序排列的整数数组，找到给定目标值的起始和终止位置。
	
	您的算法的运行时复杂度必须是O（log n）的顺序。
	
	如果在数组中找不到目标，则返回[-1，-1]。
	
	例如，
	给定[5,7,7,8,8,10]和目标值8，
	返回[3，4]。
	
解题思路
	排序！！logn！！范围！！
		看着都像二分查找
	首先，建立二元结果数组res，起点start，终点end。
	二分法求左边界：
	当中点小于target，start移向中点，否则end移向中点；
	先判断起点，再判断终点是否等于target，如果是，赋值给res[0]。
	二分法求右边界：
	当中点大于target，end移向中点，否则start移向中点；
	先判断终点，再判断起点是否等于target，如果是，赋值给res[1]。
	返回res。
 * @Date 2017-09-14 23：43
 */
public class _034_Search_for_a_Range {
	/**
	 * 二分查找
	 * @param nums
	 * @param target
	 * @return
	 */
    public int[] searchRange(int[] nums, int target) {
    	int[] rs = {-1, -1};
    	if (nums==null || nums.length<2)	return rs;
    	int len = nums.length;
    	int l = 0, r = len-1;
    	while (l <= r) {
    		int mid = l+(r-l)/2;
    		int midVal = nums[mid];
      		LogUtils.println(l+":"+l+"{}{}r:"+r);
    		LogUtils.println(mid+">>"+midVal);
    		if (midVal < target) {
    			l = mid-1;
    		} else if (midVal > target) {
    			r = mid+1;
    		} else {
    			if (nums[l] < target) l++;
    			if (nums[r] > target) r--;
//    			if (nums[l]==target && nums[r]==target) {
//    				rs[0] = l;
//    				rs[1] = r;
//    				return rs;
//    			}
    		}
    	}
        return rs;
    }
	public static void main(String[] args) {
		_034_Search_for_a_Range obj = new _034_Search_for_a_Range();

		obj.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8);
	}

}
